//Implement next permutation, which rearranges numbers into the 
//lexicographically next greater permutation of numbers. 
//
// If such an arrangement is not possible, it must rearrange it as the lowest 
//possible order (i.e., sorted in ascending order). 
//
// The replacement must be in place and use only constant extra memory. 
//
// 
// Example 1: 
// Input: nums = [1,2,3]
//Output: [1,3,2]
// Example 2: 
// Input: nums = [3,2,1]
//Output: [1,2,3]
// Example 3: 
// Input: nums = [1,1,5]
//Output: [1,5,1]
// Example 4: 
// Input: nums = [1]
//Output: [1]
// 
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 100 
// 0 <= nums[i] <= 100 
// 
// Related Topics Array Two Pointers 👍 7813 👎 2637


package leetcode.editor.en;

import java.util.Arrays;

public class _31_NextPermutation {
    public static void main(String[] args) {
        Solution solution = new _31_NextPermutation().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void nextPermutation(int[] nums) {
            for (int i = nums.length-1; i >= 0; i--) {
                if (nums[i]>nums[i-1]){
                    Arrays.sort(nums, i, nums.length);
                    for (int j = i; j < nums.length; j++) {
                        if (nums[i-1]<nums[j]){
                            int temp = nums[i - 1];
                            nums[i-1] = nums[j];
                            nums[j] = temp;
                            return;
                        }
                    }
                }
            }
            Arrays.sort(nums);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}